package com.cb2.algorithm.leetcode;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * <a href='https://leetcode.cn/problems/triangle'>三角形最小路径和(Triangle)</a>
 * <p>给定一个三角形 triangle ，找出自顶向下的最小路径和。</p>
 * <p>每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
 * 也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
 *      输出：11
 *      解释：如下面简图所示：
 *                   2
 *                  3 4
 *                 6 5 7
 *                4 1 8 3
 *          自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
 *
 *  示例 2：
 *      输入：triangle = [[-10]]
 *      输出：-10
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= triangle.length <= 200</li>
 *     <li>triangle[0].length == 1</li>
 *     <li>triangle[i].length == triangle[i - 1].length + 1</li>
 *     <li>-10^4 <= triangle[i][j] <= 10^4</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/4/30 16:51
 */
public class LC0120Triangle_M {
    static class Solution {
        /**
         * 计算三角形从顶到底的最小路径和。使用动态规划+空间优化方法解决：
         * <ol>
         *     <li>使用一维数组dp保存当前行的最小路径和</li>
         *     <li>从顶到底逐行计算，自右向左更新避免覆盖</li>
         *     <li>处理每行的首尾元素特殊情况</li>
         *     <li>最后遍历dp数组找出最小值</li>
         * </ol>
         *
         * @param triangle 三角形数据结构，每个元素为整数列表
         * @return 从顶部到底部的最小路径和
         */
        public int minimumTotal(List<List<Integer>> triangle) {
            // 三角形的高度
            int h = triangle.size();
            // 初始化dp数组，空间复杂度O(N)
            int[] dp = new int[h];
            // 逐层处理三角形
            for (int row = 0; row < h; row++) {
                // 从右向左处理，避免覆盖未使用的dp值
                for (int col = row; col >= 0; col--) {
                    int currIdxVal = triangle.get(row).get(col);
                    // 每行第一个元素：只能从上一行的第一个元素下来
                    if (col == 0) {
                        dp[col] = dp[col] + currIdxVal;
                    }
                    // 每行最后一个元素：只能从上一行的最后一个元素下来
                    else if (col == row) {
                        dp[col] = dp[col - 1] + currIdxVal;
                    }
                    // 中间元素：可以从左上或上方下来，取较小值
                    else {
                        dp[col] = Math.min(dp[col - 1], dp[col]) + currIdxVal;
                    }
                }
            }
            int res = Integer.MAX_VALUE;
            for (int i : dp) {
                res = Math.min(res, i);
            }
            return res;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.minimumTotal(Arrays.asList(Collections.singletonList(2), Arrays.asList(3, 4), Arrays.asList(6, 5, 7), Arrays.asList(4, 1, 8, 3))));
        System.out.println(solution.minimumTotal(Collections.singletonList(Collections.singletonList(-10))));
    }
}
